﻿#include"list.h"

//反转链表
// https://leetcode.cn/problems/reverse-linked-list/
// 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
//	单链表反转 迭代
//	通过按照从前到后的顺序，先将前面的反转，但总体还是一个链表
ListNode* reverseList0(ListNode* head) {
	//空链，单节点链表直接返回
	if (head == nullptr || head->next == nullptr)return head;
	ListNode* pre = head;
	ListNode* curr = pre->next;
	ListNode* next = curr->next;
	while (curr != nullptr)
	{
		curr->next = pre;
		//每次将前面已经反转的看作一个整体，则head->next为最头（最后）结点的后继
		head->next = next;

		pre = curr;
		if (next == nullptr)break;
		curr = next;
		next = curr->next;
	}
	head = curr;
	return head;
}

//	单链表反转 迭代
// 参考左神的
//	分为两个链表，一个是反转链表，一个是原链表，遍历时将原链表的头移动到反转链表的头
ListNode* reverseList1(ListNode* head) {
	ListNode* pre = nullptr;
	ListNode* next = nullptr;

	while (head != nullptr)
	{
		next = head->next;
		head->next = pre;

		pre = head;
		head = next;
	}
	return pre;
}


//	单链表反转 递归
ListNode* reverseList2(ListNode* head) {
	return head;
}

//范围反转
//https://leetcode.cn/problems/reverse-linked-list-ii/description/
ListNode* reverseBetween(ListNode* head, int left, int right) {
	if (left == right) return head; // 一个节点无需反转的情况

	ListNode dummy(0);  // 哑节点简化头节点处理 dummy 虚拟
	dummy.next = head;
	ListNode* pre = &dummy; // 反转区间的前驱节点

	// 定位到left的前一个节点
	for (int i = 0; i < left - 1; ++i) {
		pre = pre->next;
	}

	//头插法反转区间
	ListNode* curr = pre->next; // 当前要处理的节点
	ListNode* next = nullptr;	// 保存下一个待处理节点
	for (int i = 0; i < right - left; ++i) {	//反转次数为数量减一
		next = curr->next;
		curr->next = next->next;      // 将当前节点指向后续节点
		next->next = pre->next;       // 将下一个节点插入到pre之后
		pre->next = next;             // 更新pre->next的指向	即实现头插
	}

	return dummy.next;
}


//	双链表反转	迭代
DoubleListNode* reverseList(DoubleListNode* head) {
	DoubleListNode* pre = nullptr;
	DoubleListNode* next = nullptr;

	while (head != head)
	{
		next = head->next;
		head->next = pre;
		head->pre = next;

		pre = head;
		head = next;
	}
	return pre;
}


//合并两个有序链表
//https://leetcode.cn/problems/merge-two-sorted-lists/description/
//将两个升序链表合并为一个新的 升序 链表并返回
//新链表是通过拼接给定的两个链表的所有节点组成的
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
	
	ListNode dummy(0);  // 哑节点简化头节点处理 dummy 虚拟
	dummy.next = nullptr;
	ListNode* last = &dummy;
	
	ListNode* min = nullptr;

	while(list1 != nullptr && list2 != nullptr)
	{
		if (list1->val > list2->val)
		{ min = list2; list2 = list2->next;}
		else { min = list1; list1 = list1->next; }

		last->next = min;
		last = min;
	}
	last->next = list1 == nullptr ? list2 : list1;
	return dummy.next;
}


//两个链表相加
// 给你两个 非空 的链表，表示两个非负的整数
// 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字 
// 就是低位数字在前
// 请你将两个数相加，并以相同形式返回一个表示和的链表。
// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头
// 测试链接：https://leetcode.cn/problems/add-two-numbers/
//	T O(max(m,n)) S O(1)
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
	ListNode dummy(0);  // 哑节点简化头节点处理 dummy 虚拟
	dummy.next = l1;
	ListNode* last = &dummy;

	ListNode* cur1 = l1;
	ListNode* cur2 = l2;
	int ca = 0;			//进位情况
	int num = 0;
	//处理都有数字的情况
	while (cur1 != nullptr && cur2 != nullptr)
	{
		num = cur1->val + cur2->val + ca;
		cur1->val = num % 10;
		ca = num / 10;

		last = cur1;
		cur1 = cur1->next;
		cur2 = cur2->next;
	}
	//处理一个已经用尽的情况
	if (cur1 == nullptr) {
		last->next = cur2;
		while (ca && cur2 != nullptr)
		{
			num = cur2->val + ca;
			cur2->val = num % 10;
			ca = num / 10;
			last = cur2;
			cur2 = cur2->next;
		}
	}
	else while (ca && cur1 != nullptr)
	{
		num = cur1->val + ca;
		cur1->val = num % 10;
		ca = num / 10;
		last = cur1;
		cur1 = cur1->next;
	}

	//处理最后ca
	if (ca) { ListNode* end = new ListNode(ca); last->next = end; }
	return dummy.next;
}

//两个链表相加 
//高位数字在前
//给定两个 非空链表 l1和 l2 来代表两个非负整数。
// 数字最高位位于链表开始位置。它们的每个节点只存储一位数字。
// 将这两数相加会返回一个新的链表。
//可以假设除了数字 0 之外，这两个数字都不会以零开头。
//测试链接：https://leetcode.cn/problems/lMSNwu/
//提交时名字要去掉2
// 3.遍历记值，再相加		//不行，链表过长会使数字溢出
// 1.反转再相加，	T O(m)+O(n)+O(max(m,n)) S O(1)
// 2.放入两个栈，再同步弹出，	T O(2m)+O(n)+O(max(m,n)) S O(m+n)+O(max(m,n)
ListNode* addTwoNumbers2(ListNode* l1, ListNode* l2) {
	std::vector<ListNode*> s1;
	std::vector<ListNode*> s2;

	ListNode* next = l1;
	while (next != nullptr){
		s1.push_back(next);
		next = next->next;
	}

	next = l2;
	while (next != nullptr) {
		s2.push_back(next);
		next = next->next;
	}

	ListNode* head = nullptr;
	
	int a1, a2;				//l1，l2的值
	int num = 0, ca = 0;	//ca 进位信息
	ListNode* curr;
	while (!s1.empty() || !s2.empty())
	{
		if (s1.empty()) a1 = 0;else { a1 = s1.back()->val; s1.pop_back(); }
		if (s2.empty()) a2 = 0;else { a2 = s2.back()->val; s2.pop_back(); }
		
		num = a1 + a2 + ca;
		ca = num / 10;
		curr = new ListNode(num % 10);

		curr->next = head;
		head = curr;
	}

	if (ca) { curr = new ListNode(ca); curr->next = head;head = curr;}
	return head;
}

// 划分链表
// 给你一个链表的头节点 head 和一个特定值 x
// 请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
// 你应当 保留 两个分区中每个节点的初始相对位置
// 测试链接 : https://leetcode.cn/problems/partition-list/
ListNode* partition(ListNode* head, int x) {
	ListNode dummy(0);
	dummy.next = nullptr;
	ListNode* last = &dummy;
	
	ListNode dummy2(0);
	dummy2.next = head;
	ListNode* pre = &dummy2;
	
	ListNode* curr = head;
	while (curr != nullptr) {
		if (curr->val < x) {
			//从旧链表移除
			pre->next = curr->next;

			//加到新链
			last->next = curr;
			last = curr;
		}
		else pre = curr;
		curr = curr->next;
	}

	last->next = dummy2.next;
	return dummy.next;
}

//以下要求空间S O(1)

//题目1: 返回两个无环链表相交的第一个节点
// 返回两个无环链表相交的第一个节点
// 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
	//通过计数来实现，l1,l2,长的想跑到短的开始，相同的第一个就是答案
	//T O(2m+n)	S O(1)
	ListNode dummy(0);
	ListNode* ans = &dummy;
	int size1 = 0;
	int size2 = 0;
	ListNode* l1 = headA;
	ListNode* l2 = headB;
	while (l1 != nullptr){l1 = l1->next;size1++;}
	while (l2 != nullptr){l2 = l2->next;size2++;}
	l1 = headA;
	l2 = headB;
	while (size1 > size2) { l1 = l1->next; size1--; }
	while (size1 < size2) { l2 = l2->next; size2--; }

	while (l1 != l2) {l1 = l1->next; l2 = l2->next;}
	if (l1 == l2)ans = l1;
	return ans;
}

//题目2: 每k个节点一组翻转链表
// 每k个节点一组翻转链表
// k 是一个正整数，它的值小于或等于链表的长度。
// 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
// 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
//一次遍历，K个一计数
ListNode* reverseKGroup(ListNode* head, int k){
	if (k == 1)return head;
	if (head == nullptr || head->next == nullptr)return head;
	
	ListNode dummy(0);
	dummy.next = head;
	ListNode* pre = &dummy;

	int num = 1;
	//记录每个段开始的前一个地址，然后最后不够的话再反转回去
	ListNode* last = head;
	ListNode* next = nullptr;
	while (last != nullptr && last->next != nullptr) {
		next = last->next;
		last->next = next->next;      
		next->next = pre->next;       
		pre->next = next;             

		num++;
		if (num == k) { num = 1; pre = last; last = last->next; }
	}
	if(num != 1){
		last = pre->next;
		while (last != nullptr && last->next != nullptr) {
			next = last->next;
			last->next = next->next;
			next->next = pre->next;
			pre->next = next;
		}
	}

	return dummy.next;
}

//题目3: 复制带随机指针的链表
// 复制带随机指针的链表
// 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/
//由于随机指针指向的结点无法定位的问题，
//那麽我们就要让新链表和旧链表相关联来确定随机指针指向的结点的问题
//因此有 1 -> 1' -> 2 -> 2' -> 3 ··· 
//再对他们进行分离就好了
//分离时 将复制的随机指针指向，随机指针的结点的下一个
Node* copyRandomList(Node* head){
	if (head == nullptr)return head;
	
	Node* ans = nullptr;
	Node* curr = head;
	Node* next = head->next;
	//复制节点实现 1 -> 1' -> 2 -> 2' -> 3 ··· 
	while (curr != nullptr) {
		next = curr->next;					//记录下一个节点
		curr->next = new Node(curr->val);	//对本节点进行复制
		curr->next->next = next;			//将创建的新节点的next指向下一个节点
		curr = next;						//换到下一个节点
	}
	//复制随机指针	含有回指的可能不能在此分离
	curr = head;
	next = nullptr;
	while (curr != nullptr) {
		next = curr->next->next;
		curr->next->random = curr->random == nullptr ? nullptr: curr->random->next;	//新节点的random
		curr = next;
	}
	//分离链表
	ans = head->next;
	curr = head;
	next = nullptr;
	while (curr != nullptr) {
		next = curr->next->next;
		curr->next->next = next == nullptr ? nullptr : next->next;				
		curr->next = next;
		curr = next;
	}
	return ans;
}

//题目4: 判断链表是否是回文结构。这个题的流程设计甚至是考研常用。快慢指针找中点。
// 判断链表是否是回文结构
// 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/
bool isPalindrome(ListNode* head){
	if (head == nullptr || head->next == nullptr)return true;
	bool ans = true;
	ListNode* k = head;
	ListNode* m = head;
	//快慢指针确定中点
	while (k != nullptr) {
		if (k->next == nullptr || k->next->next == nullptr) break;
		k = k->next->next;
		m = m->next;
	}
	//将后段进行反转
	ListNode* last = m->next;
	ListNode* next = nullptr;
	while (last != nullptr && last->next != nullptr) {
		next = last->next;
		last->next = next->next;
		next->next = m->next;
		m->next = next;
	}
	//比较确定是否为回文
	k = head;
	ListNode* curr = m->next;
	while (curr != nullptr) {
		if (k->val != curr->val) { ans = false; break; }
		curr = curr->next;
		k = k->next;
	}
	//将后段进行反转回原本
	last = m->next;
	next = nullptr;
	while (last != nullptr && last->next != nullptr) {
		next = last->next;
		last->next = next->next;
		next->next = m->next;
		m->next = next;
	}
	return ans;
}

//题目5: 返回链表的第一个入环节点。快慢指针找中点。
// 返回链表的第一个入环节点
// 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/
//设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。
//此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。
//任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。
//因此，我们有a + (n + 1)b + nc = 2(a + b)⟹a = c + (n−1)(b + c)
//有了 a = c + (n−1)(b + c) 的等量关系，
//我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。
ListNode* detectCycle(ListNode* head){
	if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {
		return nullptr;
	}
	ListNode* slow = head->next;
	ListNode* fast = head->next->next;
	while (slow != fast) {
		if (fast->next == nullptr || fast->next->next == nullptr) {
			return nullptr;
		}
		slow = slow->next;
		fast = fast->next->next;
	}
	fast = head;
	while (slow != fast) {
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}

//题目6: 在链表上排序。要求时间复杂度O(n* log n)，额外空间复杂度O(1)，还要求排序有稳定性。
// 排序链表
// 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
// 即归并
// 数组排序做不到，链表排序可以
// 测试链接 : https://leetcode.cn/problems/sort-list/
ListNode* sortList(ListNode* head){

}
